package org.example.Soution002;

import java.util.*;

public class RottingOrangePro {
    public static void main(String[] args) {
        RottingOrangePro orange = new RottingOrangePro();
//        int[][] grid={{2,1,1},{1,1,1},{0,1,2}};
//        int[][] grid={
//                {2,0,1,1,1,1,1,1,1,1},
//                {1,0,1,0,0,0,0,0,0,1},
//                {1,0,1,0,1,1,1,1,0,1},
//                {1,0,1,0,1,0,0,1,0,1},
//                {1,0,1,0,1,0,0,1,0,1},
//                {1,0,1,0,1,1,0,1,0,1},
//                {1,0,1,0,0,0,0,1,0,1},
//                {1,0,1,1,1,1,1,1,0,1},
//                {1,0,0,0,0,0,0,0,0,1},
//                {1,1,1,1,1,1,1,1,1,1}
//        };
        int[][] grid={{0,1,1,2,1,1,1}};
        System.out.println(orange.orangesRotting(grid));
    }

    int[] pr={-1,0,1,0};
    int[] pc={0,-1,0,1};
    public int orangesRotting(int[][] grid) {
        Queue<Integer> queue=new LinkedList<>();  //用来进行广度优先遍历
        Map<Integer,Integer> map=new HashMap<>(); //用来获取层数
        int C=grid.length; int R=grid[0].length;
        //初始化腐烂橘子
        for(int i=0;i<C;i++){
            for(int j=0;j<R;j++){
                if(grid[i][j]==2){
                    queue.add(i*R+j);
                    map.put(i*R+j,0);
                }
            }
        }

        int ans=0;
        while(!queue.isEmpty()){
            int temp=queue.poll();
            //获取腐烂橘子的坐标
            int c=temp/R; int r=temp%R;
            for(int k=0;k<4;k++){
                int nc=c+pc[k];
                int nr=r+pr[k];
                if(nc>=0&&nc<C&&nr>=0&&nr<R&&grid[nc][nr]==1){
                    grid[nc][nr]=2;
                    queue.add(nc*R+nr);
                    map.put(nc*R+nr,map.get(c*R+r)+1);
                    ans=map.get(nc*R+nr);
                }
            }
        }
        for(int[] tmp:grid){
            for(int t:tmp){
                if(t==1){
                    return -1;
                }
            }
        }
        return ans;
    }
}
